{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Video Stitching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: videoStitching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #视频拼接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你将会获得一系列视频片段，这些片段来自于一项持续时长为&nbsp;<code>time</code>&nbsp;秒的体育赛事。这些片段可能有所重叠，也可能长度不一。</p>\n",
    "\n",
    "<p>使用数组&nbsp;<code>clips</code> 描述所有的视频片段，其中 <code>clips[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> 表示：某个视频片段开始于&nbsp;<code>start<sub>i</sub></code>&nbsp;并于&nbsp;<code>end<sub>i</sub></code>&nbsp;结束。</p>\n",
    "\n",
    "<p>甚至可以对这些片段自由地再剪辑：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，片段&nbsp;<code>[0, 7]</code>&nbsp;可以剪切成&nbsp;<code>[0, 1] +&nbsp;[1, 3] + [3, 7]</code>&nbsp;三部分。</li>\n",
    "</ul>\n",
    "\n",
    "<p>我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（<code>[0, time]</code>）。返回所需片段的最小数目，如果无法完成该任务，则返回&nbsp;<code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "选中 [0,2], [8,10], [1,9] 这三个片段。\n",
    "然后，按下面的方案重制比赛片段：\n",
    "将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。\n",
    "现在手上的片段为 [0,2] + [2,8] + [8,10]，而这些覆盖了整场比赛 [0, 10]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>clips = [[0,1],[1,2]], time = 5\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>\n",
    "无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释： </strong>\n",
    "选取片段 [0,4], [4,7] 和 [6,9] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= clips.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= time &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [video-stitching](https://leetcode.cn/problems/video-stitching/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [video-stitching](https://leetcode.cn/problems/video-stitching/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]\\n10', '[[0,1],[1,2]]\\n5', '[[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]]\\n9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        last = ret = pre = 0\n",
    "        for a, b in clips:\n",
    "            if a < time:\n",
    "                maxn[a] = max(maxn[a], b)\n",
    "        \n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp = [0] + [float(\"inf\")] * time\n",
    "        for i in range(1, time + 1):\n",
    "            for aj, bj in clips:\n",
    "                if aj < i <= bj:\n",
    "                    dp[i] = min(dp[i], dp[aj] + 1)\n",
    "        \n",
    "        return -1 if dp[time] == float(\"inf\") else dp[time]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxnum=0\n",
    "        for i in range(len(clips)):\n",
    "            if clips[i][0]==0:\n",
    "                maxnum=max(clips[i][1],maxnum)\n",
    "        l=[]\n",
    "        l.append([0,maxnum])\n",
    "        maxnum2=0\n",
    "        t=0\n",
    "        while maxnum<time:\n",
    "            for i in range(len(clips)):\n",
    "                if clips[i][0]<=maxnum and clips[i][1]>maxnum2:\n",
    "                    t=i\n",
    "                    maxnum2=clips[i][1]\n",
    "            l.append(clips[t])\n",
    "            if maxnum==maxnum2:\n",
    "                return -1\n",
    "            maxnum=maxnum2\n",
    "        return len(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        f = [0] * (time + 1)\n",
    "        for st, end in clips:\n",
    "            if st <= time:\n",
    "                f[st] = max(f[st], end)\n",
    "        \n",
    "        end, next_end, cnt = 0, 0, 0\n",
    "        for i, x in enumerate(f):\n",
    "            next_end = max(next_end, x)\n",
    "            if i == end:\n",
    "                cnt += 1\n",
    "                if next_end >= time:\n",
    "                    return cnt\n",
    "                elif next_end == end:\n",
    "                    return -1\n",
    "                end = next_end\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        # 动态规划还是很6a\n",
    "        dp = [666]*(time+1)\n",
    "        dp[0]=0\n",
    "        for i in range(1,time+1):\n",
    "            for clip in clips:\n",
    "                if clip[0]<i<=clip[1]: #当前在clip区间内\n",
    "                    dp[i] = min(dp[i],dp[clip[0]]+1)\n",
    "        return dp[time] if dp[time]!=666 else -1\n",
    "\n",
    "        # 贪心会有中间重复的区间\n",
    "        # # myclips = sorted()\n",
    "        # def eraseOverlapIntervals(args_doublelist):\n",
    "        #     sorted_doublelist = sorted(args_doublelist)\n",
    "        #     lent = len(args_doublelist)\n",
    "        #     res = lent\n",
    "        #     for i in range(1,lent-1):\n",
    "        #         if sorted_doublelist[i+1][0]<=sorted_doublelist[i-1][1] and sorted_doublelist[i+1][1]>=sorted_doublelist[i][1]:\n",
    "        #         # if sorted_doublelist[i-1][0] <sorted_doublelist[i][0]<sorted_doublelist[i-1][1] and sorted_doublelist[i+1][0]<sorted_doublelist[i][1]<sorted_doublelist[i+1][1]:\n",
    "        #             res-=1\n",
    "        #     return res\n",
    "        #     # curEnd = sorted_doublelist[0]\n",
    "\n",
    "        # mydict = defaultdict(list)\n",
    "        # maxt = 0\n",
    "        # for lis in clips:\n",
    "        #     maxt = max(maxt,lis[1])\n",
    "        #     mydict[lis[0]].append(lis[1])\n",
    "        # if maxt<time:\n",
    "        #     return -1\n",
    "        # count = 0\n",
    "        # maxtime = 0\n",
    "        # res = []\n",
    "        # while maxtime<time:\n",
    "        #     for keyval in sorted(mydict.keys()):\n",
    "        #         if keyval >maxtime:\n",
    "        #             return -1\n",
    "        #         else:\n",
    "        #             temp = max(mydict[keyval]) \n",
    "        #             if temp<=maxtime:\n",
    "        #                 continue\n",
    "        #             else:\n",
    "        #                 count+=1\n",
    "        #                 maxtime=temp\n",
    "        #                 res.append([keyval,temp])\n",
    "        \n",
    "        # return min(count,eraseOverlapIntervals(res))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        most_right = [0] * time\n",
    "        for L, R in clips:\n",
    "            if L < time:\n",
    "                most_right[L] = max(most_right[L], R)\n",
    "\n",
    "        step = 0  # 所需个数\n",
    "        cur_can_right = 0  #目前能到达的最远时间\n",
    "        nxt_start = 0   \n",
    "        for i in range(time):\n",
    "            cur_can_right = max(cur_can_right, most_right[i])\n",
    "            if i == nxt_start:  \n",
    "                if not (i < cur_can_right): \n",
    "                    return -1\n",
    "                nxt_start = cur_can_right  \n",
    "                step += 1\n",
    "\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "#         f = [inf] * (time + 1)\n",
    "#         f[0] = 0\n",
    "#         for i in range(1, time + 1):\n",
    "#             for l, r in clips:\n",
    "#                 if l < i <= r:\n",
    "#                     f[i] = min(f[i], f[l] + 1)\n",
    "#         return f[time] if f[time] < inf else -1\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        for l, r in clips: mp[l] = max(mp[l], r)\n",
    "\n",
    "        pre, r = 0, 0\n",
    "        ans = 0\n",
    "        for i in range(time):\n",
    "            r = max(r, mp[i])\n",
    "            if i == r: return -1\n",
    "            if i == pre:\n",
    "                ans += 1\n",
    "                pre = r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "     \n",
    "        INT_MAX = 2 ** 31 - 1\n",
    "        dp = [INT_MAX for _ in range(time + 1)]  # 0 到 i 所需要的最少区间数量\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1, time + 1):\n",
    "            for s, e in clips:\n",
    "                if s < i <= e:\n",
    "                    dp[i] = min(dp[i], dp[s] + 1)\n",
    "        \n",
    "        return dp[time] if dp[time] != INT_MAX else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        last = ret = pre = 0\n",
    "        for a, b in clips:\n",
    "            if a < time:\n",
    "                maxn[a] = max(maxn[a], b)\n",
    "        \n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        \n",
    "        return ret\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "\n",
    "        \n",
    "        dp = [sys.maxsize for i in range(time + 1)]\n",
    "        dp[0] = 0\n",
    "        for i in range(1, time + 1):\n",
    "            for clip in clips:\n",
    "                if clip[0] <= i <= clip[1]:\n",
    "                    dp[i] = min(dp[i], dp[clip[0]] + 1)\n",
    "\n",
    "        return dp[time] if dp[time] != sys.maxsize else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        \n",
    "        maxn = [0]*(time)\n",
    "        for start,end in clips:\n",
    "            if start<time:\n",
    "                maxn[start]=max(maxn[start],end)\n",
    "        \n",
    "        res = 0\n",
    "        last = 0\n",
    "        prev = 0\n",
    "        for i in range(time):\n",
    "            last = max(last,maxn[i])\n",
    "            if i>=last:\n",
    "                return -1\n",
    "            if i==prev:\n",
    "                prev = last\n",
    "                res+=1\n",
    "        return res \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "      dp = [0] + [float(\"inf\")]*time\n",
    "      for cur_time_end in range(1,time+1):\n",
    "        for clip in clips:\n",
    "          if clip[0] < cur_time_end <= clip[1]:\n",
    "            dp[cur_time_end] = min(dp[cur_time_end],1+dp[clip[0]])\n",
    "      \n",
    "      if dp[-1] == float(\"inf\"):\n",
    "        return -1\n",
    "      else:\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxReachArray = [0] * (time+1)\n",
    "        maxReach = 0\n",
    "        pre = 0\n",
    "        res = 0\n",
    "\n",
    "        for start, end in clips:\n",
    "            if start > time:\n",
    "                continue\n",
    "            maxReachArray[start] = max(maxReachArray[start], end)\n",
    "        # print(maxReachArray)\n",
    "        for i in range(time):\n",
    "            maxReach = max(maxReach, maxReachArray[i])\n",
    "            # print(i, pre, maxReach)\n",
    "            if i == maxReach:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                res += 1\n",
    "                pre = maxReach\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort()       \n",
    "        maxn=[0]*time\n",
    "        pre=0\n",
    "        last=0\n",
    "        res=0 \n",
    "        for a,b in clips:\n",
    "            if a<time:\n",
    "                maxn[a]=max(maxn[a],b)\n",
    "        for i in range(time):\n",
    "            last=max(last,maxn[i])\n",
    "            if i==last:\n",
    "                return -1\n",
    "            if i==pre:\n",
    "                res+=1\n",
    "                pre=last\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        n = len(clips)\n",
    "        dp = [0]+[101]*(time)\n",
    "        for i in range(1,time+1):\n",
    "            for j in range(n):\n",
    "                if i>clips[j][0] and i<=clips[j][1]:\n",
    "                    dp[i] = min(dp[clips[j][0]]+1,dp[i])\n",
    "        return dp[time] if dp[time]<101 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        last = ret = pre = 0\n",
    "        for a, b in clips:\n",
    "            if a < time:\n",
    "                maxn[a] = max(maxn[a], b)\n",
    "        \n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        max_range = [0] * time\n",
    "        for start, end in clips:\n",
    "            if start < time:\n",
    "                max_range[start] = max(max_range[start], end)\n",
    "        # if 0 not in max_range.keys():\n",
    "        #     return -1\n",
    "        left, end = 0, max_range[0]\n",
    "        ans = 1\n",
    "        while end < time:\n",
    "            new_end = end\n",
    "            for time_i in range(left + 1, end + 1):\n",
    "                new_end = max(new_end, max_range[time_i])\n",
    "            if new_end == end:\n",
    "                return -1\n",
    "            left, end = end, new_end\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips=sorted(clips)\n",
    "        if(clips[0][0]!=0):return -1\n",
    "        needed=[]\n",
    "        start=clips[0]\n",
    "        for ele in clips:\n",
    "            if(ele[0]!=start[0]):\n",
    "                needed.append(start)\n",
    "                start=ele\n",
    "            else:\n",
    "                if(ele[1]>start[1]):\n",
    "                    start=ele\n",
    "        needed.append(start)\n",
    "        ans=1\n",
    "        ind=1\n",
    "        prev_end=needed[0][1]\n",
    "        while ind<len(needed):\n",
    "            if(prev_end>=time):return ans\n",
    "            max_end=needed[ind][1]\n",
    "            if(needed[ind][0]>prev_end):return -1\n",
    "            while ind<len(needed) and needed[ind][0]<=prev_end :\n",
    "                curr=needed[ind]\n",
    "                max_end=max(curr[1],max_end)\n",
    "                ind+=1\n",
    "            prev_end=max_end\n",
    "            ans+=1\n",
    "        if(prev_end>=time):return ans\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        clips.sort()\n",
    "        pre, ret, last = 0, 0, 0\n",
    "\n",
    "        for start, end in clips:\n",
    "            if start < time:\n",
    "                maxn[start] = max(maxn[start], end)\n",
    "\n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        \n",
    "        return ret\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        max_right = [0 for _ in range(time)]\n",
    "        for s, e in clips:\n",
    "            if s < time:\n",
    "                max_right[s] = max(max_right[s], e)\n",
    "\n",
    "        ans, last, pre = 0, 0, 0\n",
    "        for i in range(time):\n",
    "            last = max(last, max_right[i])\n",
    "            \n",
    "            # 当前区间用完，启用下一个区间\n",
    "            if i == pre:\n",
    "                ans += 1\n",
    "                pre = last\n",
    "\n",
    "            # time大于最后一个区间了，没有区间对得上\n",
    "            if i >= last: return -1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], T: int) -> int:\n",
    "        dp = [101]*(T+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1,T+1):\n",
    "            for ch in clips:\n",
    "                if ch[0] < i <= ch[1]:\n",
    "                    dp[i] = min(dp[i],dp[ch[0]]+1)\n",
    "        return dp[T] if dp[T]!=101 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp = [0] + [float(\"inf\")] * time\n",
    "        for i in range(1, time + 1):\n",
    "            for aj, bj in clips:\n",
    "                if aj < i <= bj: # [0, 1],[1, 2]可以，[0, 1], [2, 3]不可以\n",
    "                    dp[i] = min(dp[i], dp[aj] + 1)\n",
    "        return -1 if dp[time] == float(\"inf\") else dp[time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        a = [0] * time\n",
    "        ans = 1\n",
    "        for x,y in clips:\n",
    "            if x < time:\n",
    "                a[x] = max(a[x],y)\n",
    "        def check(x:int) -> int:\n",
    "            for i in range(min(len(a),x)):\n",
    "                if a[i] >= x:\n",
    "                    return i\n",
    "            return -1\n",
    "        j = check(time)\n",
    "        while j > 0:\n",
    "            ans += 1\n",
    "            j = check(j)\n",
    "        if j == -1:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips, T):\n",
    "        dp = [0] * 101\n",
    "        mx = ans = pre = 0\n",
    "\n",
    "        for clip in clips:\n",
    "            dp[clip[0]] = max(dp[clip[0]], clip[1])\n",
    "\n",
    "        for i in range(T):\n",
    "            mx = max(mx, dp[i])\n",
    "            if i == pre:\n",
    "                ans += 1\n",
    "                pre = mx\n",
    "            if i == mx:\n",
    "                return -1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        # clips.sort(key=lambda x:x[0])\n",
    "        # print(clips)\n",
    "        # if clips[0][0] > 0:\n",
    "        #     return -1\n",
    "        # n = len(clips)\n",
    "        # ed = 0\n",
    "        # res = 0\n",
    "        # right_most = 0\n",
    "        # for i in range(n):\n",
    "        #     # do not need to select, find the right most\n",
    "        #     if clips[i][0] <= ed:\n",
    "        #         right_most = max(right_most, clips[i][1])\n",
    "        #         # if can early stop...\n",
    "        #         if right_most >= time:\n",
    "        #             break\n",
    "        #         continue\n",
    "        #     # not overlap, must select the right most\n",
    "        #     ed = right_most\n",
    "        #     # if still not overlap\n",
    "        #     if clips[i][0] > ed:\n",
    "        #         return -1\n",
    "        #     res += 1\n",
    "        #     right_most = max(right_most, clips[i][1])\n",
    "        #     if right_most >= time:\n",
    "        #         break\n",
    "        # if ed < time and right_most >= time:\n",
    "        #     res += 1\n",
    "        # return res if right_most >= time else -1\n",
    "            \n",
    "        n = len(clips)\n",
    "        dp = [101]*(time+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, time+1):\n",
    "            for a, b in clips:\n",
    "                if a<=i and i <= b:\n",
    "                    dp[i] = min(dp[i], dp[a] + 1)\n",
    "        return dp[time] if dp[time] < 101 else -1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        n = len(clips)\n",
    "        maxr = [0] * time\n",
    "        last = res = pre = 0\n",
    "        for i,j in clips:\n",
    "            if i < time:\n",
    "                maxr[i] = max(maxr[i], j)\n",
    "        for i in range(time):\n",
    "            last = max(last, maxr[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if pre == i:\n",
    "                res += 1\n",
    "                pre = last\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        nums = [0] * (time + 1)\n",
    "        for start, end in clips:\n",
    "            if start > time: continue\n",
    "            nums[start] = max(nums[start], end - start)\n",
    "\n",
    "        n = len(nums)\n",
    "        steps = 0\n",
    "        this_jump_end = 0\n",
    "        furthest_position = 0\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            furthest_position = max(furthest_position, i + nums[i])\n",
    "            if i == furthest_position:\n",
    "                return -1\n",
    "            if i == this_jump_end:\n",
    "                this_jump_end = furthest_position\n",
    "                steps += 1\n",
    "\n",
    "        return steps\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        if 0 == time:\n",
    "            return 0\n",
    "        clips.sort(key=lambda x: [x[0], -x[1]])\n",
    "        res = 0\n",
    "        n = len(clips)\n",
    "        left, right = clips[0][0], clips[0][1]\n",
    "        cur_end, next_end = 0, 0\n",
    "        i = 0\n",
    "        while i<n and  clips[i][0] <= cur_end:\n",
    "            while i < n and clips[i][0] <= cur_end:\n",
    "                next_end = max(next_end, clips[i][1])\n",
    "                i += 1\n",
    "            res += 1\n",
    "            cur_end = next_end\n",
    "            if cur_end >= time:\n",
    "                return res\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort(key=lambda x:(x[0], -x[1]))\n",
    "\n",
    "        res = 0\n",
    "        cur, nxt = 0, 0\n",
    "        i, n = 0, len(clips)\n",
    "\n",
    "        while i < n and clips[i][0] <= cur:\n",
    "            while i < n and clips[i][0] <= cur:\n",
    "                nxt = max(nxt, clips[i][1])\n",
    "                i += 1\n",
    "\n",
    "            res += 1\n",
    "            cur = nxt\n",
    "            if cur >= time:\n",
    "                return res\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp = [0] + [float(\"inf\")] * time\n",
    "        print(dp)\n",
    "        for i in range(1, time + 1):\n",
    "            for aj, bj in clips:\n",
    "                if aj <= i <= bj:\n",
    "                    dp[i] = min(dp[i], dp[aj] + 1)\n",
    "        \n",
    "        return -1 if dp[time] == float(\"inf\") else dp[time]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], T: int) -> int:\n",
    "        # dp[i]代表覆盖[0, i]的最小区间数\n",
    "        dp =[float('inf')] * (T + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, T + 1):\n",
    "            for clip in clips:\n",
    "                # 找到包含结束端点的视频片段\n",
    "                if (clip[0] < i <= clip[1]):\n",
    "                    # 覆盖 (0 - clip[0]) 区间的视频的最小片段数量 \n",
    "                    dp[i] = min(dp[i], dp[clip[0]] + 1)\n",
    "        return -1 if (dp[T] == float('inf')) else dp[T]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        \"\"\"\n",
    "        题意:time: 要求完成time秒时长的内容; 片段[start, end]表示从第start秒开始, 到end秒结束(不包括第end秒), 片段内一共有end-start秒内容\n",
    "        动态方程:dp[i]: 完成第i秒, 最少需要的片段数, i:[0,time)\n",
    "        假设当前遍历的片段为[start, end], dp[i] = dp[start-1]+1\n",
    "        \"\"\"\n",
    "        clips.sort(key=lambda x: (x[0], -x[1]))  # 片段按照最早开始时间及最晚结束时间 来排序\n",
    "        dp = [0] * time  # dp[i]:完成第i秒, 最少需要的片段数\n",
    "\n",
    "        # 记录当前已知的最晚结束时间. 即在第lastEnd秒时结束(不包括第lastEnd秒), 表明下一个片段最晚要在第lastEnd秒开始, 否则衔接不上\n",
    "        lastEnd = 0\n",
    "        for start, end in clips:  # 遍历每个片段\n",
    "            # 如果当前片段开始时间大于之前最晚结束时间, 说明无法衔接上; 如果开始时间大于等于time, 说明已经超过要求的时间# finished@Time:2023-10-13 13:52\n",
    "            # 直接退出循环\n",
    "            if start > lastEnd or start >= time:\n",
    "                break\n",
    "            # 如果当前片段的结束时间还早于或等于之前记录的最晚结束时间,直接跳过不用考虑\n",
    "            if end <= lastEnd:\n",
    "                continue\n",
    "            # 开始计算\n",
    "            for i in range(lastEnd, min(time, end)):\n",
    "                # 完成第i秒视频, 需要的最少片段数\n",
    "                dp[i] = dp[start-1] + 1\n",
    "            # 更新最晚结束时间\n",
    "            lastEnd = max(lastEnd, end)\n",
    "        # print(dp)\n",
    "        return dp[time-1] if dp[time-1] != 0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        last = ret = pre = 0\n",
    "        for a, b in clips:\n",
    "            if a < time:\n",
    "                maxn[a] = max(maxn[a], b)\n",
    "        \n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        # dp[i]: 覆盖时长为i的视频至少需要多少个片段\n",
    "        dp = [0] + [float('inf')]*time\n",
    "        for t in range(1, time+1):\n",
    "            for start, end in clips:\n",
    "                if start <= t <= end:\n",
    "                    dp[t] = min(dp[t], dp[start] + 1)\n",
    "        \n",
    "        return -1 if dp[time] == float('inf') else dp[time]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self,clips:List[List[int]], time:int)->int:\n",
    "        n=len(clips)\n",
    "        clips.sort(key=lambda x:x[0])   #按左端点递增排序\n",
    "        ans=0                       #存放答案\n",
    "        preend=0       #当前片段的右端点\n",
    "        i=0\n",
    "        while preend<time:\n",
    "            next=preend         #下一个片段的右端点\n",
    "            while i<n and clips[i][0]<=preend:    #重叠\n",
    "                next=max(next,clips[i][1])        #取最大的右端点\n",
    "                i+=1\n",
    "            if next==preend:  #找不到新片段，无法合成视频\n",
    "                return -1\n",
    "            preend=next\n",
    "            ans+=1              #选择clips[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort()\n",
    "        n = len(clips)\n",
    "        \n",
    "        dp = [inf] * (time + 1)\n",
    "        dp[0] = 0\n",
    "        while clips:\n",
    "            start, end = clips.pop(0)\n",
    "            if start > time:\n",
    "                break\n",
    "            for i in range(start, end + 1):\n",
    "                if i > time:\n",
    "                    break\n",
    "                dp[i] = min(dp[i], dp[start] + 1)\n",
    "            \n",
    "        return dp[time] if dp[time] != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        \n",
    "        # 动态规划思想\n",
    "        n = len(clips)\n",
    "        clips.sort()\n",
    "        dp = [0]+[n+1]*(time)\n",
    "        for i in range(1,time+1):\n",
    "            for aj,bj in clips:\n",
    "                if aj <= i <= bj:\n",
    "                    dp[i] = min(dp[i],dp[aj]+1)\n",
    "        return -1 if dp[time] == n+1 else dp[time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp = [0] + [float('inf')] * time\n",
    "        for i in range(1, time+1):\n",
    "            for start, end in clips:\n",
    "                if start < i <= end:\n",
    "                    dp[i] = min(dp[i], dp[start] + 1)\n",
    "\n",
    "        return -1 if dp[time] == float(\"inf\") else dp[time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips = sorted(clips, key=lambda it: (it[0], -it[1]))\n",
    "        tail = 0\n",
    "        next_tail = 0\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while i < len(clips) and clips[i][0] <= tail:\n",
    "            while i < len(clips) and clips[i][0] <= tail:\n",
    "                next_tail = max(next_tail, clips[i][1])\n",
    "                i += 1\n",
    "            tail = next_tail\n",
    "            cnt += 1\n",
    "            if tail >= time:\n",
    "                return cnt\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        last = ret = pre = 0\n",
    "        for a, b in clips:\n",
    "            if a < time:\n",
    "                maxn[a] = max(maxn[a], b)\n",
    "        \n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    贪心\n",
    "    和https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/思路完全一致\n",
    "    1.记录某一个开始节点能到的最远距离mx\n",
    "    2.依次遍历time，然后取对应时间点最远能到距离，更新至nxt，表示下一轮跳跃能跳跃到的最远距离，比如\n",
    "    |-------|--|--|------|--|\n",
    "    a       b  c  d      e  f\n",
    "    假设三段[a, d], [b, e], [d, f]，在[a, d]中遍历的时候先遍历到b，nxt被替换成e，然后没到d的时候又碰到了c，nxt被\n",
    "    替换成f，但是只有遍历到d的时候才会答案+1（这个思路如何用代码表述出来非常关键！！！）\n",
    "    '''\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        n = len(clips)\n",
    "        mx = [0] * (time + 1)\n",
    "        for a, b in clips:\n",
    "            if a > time:\n",
    "                continue\n",
    "            mx[a] = max(mx[a], b)\n",
    "        \n",
    "        cur, nxt = 0, 0\n",
    "        res = 0\n",
    "        for i in range(time):\n",
    "            nxt = max(nxt, mx[i])\n",
    "            if i == nxt:\n",
    "                return -1\n",
    "            if i == cur:\n",
    "                res += 1\n",
    "                cur = nxt\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp=[0]+[float(\"inf\")]*time\n",
    "        for i in range(1,time+1):\n",
    "            for ja,jb in clips:\n",
    "                if ja<i<=jb:\n",
    "                    dp[i]=min(dp[i],dp[ja]+1)\n",
    "        return -1 if dp[time]==float(\"inf\")else dp[time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp = [0] + [inf] * time\n",
    "        for i in range(1,time + 1):\n",
    "            for l,r in clips:\n",
    "                if l <= i <= r:\n",
    "                    dp[i] = min(dp[i],dp[l] + 1)\n",
    "        return dp[-1] if dp[-1] != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        ###clips根据开始时间正序排列，以及结束时间倒叙排列\n",
    "        clips.sort(key = lambda x:(x[0],-x[1]))\n",
    "        ##初始化cur_end\n",
    "        start = clips[0][0]\n",
    "        if start != 0:\n",
    "            return -1\n",
    "        cur_end = clips[0][1]\n",
    "        if cur_end >= time:\n",
    "            return 1\n",
    "        # 记录选择的短视频个数\n",
    "        count = 1\n",
    "        # 记录当前视频序号，从第二个开始\n",
    "        i = 1\n",
    "        ##初始化next_end\n",
    "        next_end = 0\n",
    "        n = len(clips)\n",
    "        ##当满足下一个视频的开始小于当前结束，且当前视频序号在总数以内\n",
    "        while i<n and clips[i][0] <=  cur_end:\n",
    "             ##比较所有起点在当前结束之前的时间，寻找下一个视频最大的结束点\n",
    "            while i<n and clips[i][0] <=  cur_end:\n",
    "                next_end = max(next_end,clips[i][1])\n",
    "                i += 1\n",
    "            ##找到下一个视频最大的结束点，数量加一，下一个结束点变为当前结束点\n",
    "            count += 1\n",
    "            cur_end = next_end\n",
    "            ##如果当前结束点大于等于时间段，则返回结果\n",
    "            if cur_end >= time:\n",
    "                return count\n",
    "        ##遍历完成，都不满足，则返回-1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        last = ret = pre = 0\n",
    "        for a, b in clips:\n",
    "            if a < time:\n",
    "                maxn[a] = max(maxn[a], b)\n",
    "        \n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "\n",
    "\n",
    "        clips.sort()\n",
    "        m=len(clips)\n",
    "        if time == 0:\n",
    "            return 0\n",
    "        right=0\n",
    "        Max=0\n",
    "        num=0\n",
    "        i=0\n",
    "        while i < m:\n",
    "            if clips[i][0] <= right:\n",
    "                if clips[i][1] > right:\n",
    "                    Max=max(Max,clips[i][1])\n",
    "                    if Max >= time:\n",
    "                        return num+1\n",
    "                i+=1\n",
    "            else:\n",
    "                if Max == 0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    num+=1\n",
    "                    right=Max\n",
    "                    Max=0\n",
    "        return -1\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], T: int) -> int:\n",
    "        clips.sort(key=lambda x: x[0])  # 按照起始时间排序\n",
    "        end, count, i = 0, 0, 0\n",
    "        \n",
    "        while end < T:\n",
    "            max_end = end\n",
    "            while i < len(clips) and clips[i][0] <= end:\n",
    "                max_end = max(max_end, clips[i][1])\n",
    "                i += 1\n",
    "            if max_end == end:  # 无法找到符合条件的片段\n",
    "                return -1\n",
    "            end = max_end\n",
    "            count += 1\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp = [0] + [float(\"inf\")] * time\n",
    "        for i in range(1, time + 1):\n",
    "            for aj, bj in clips:\n",
    "                if aj < i <= bj:\n",
    "                    dp[i] = min(dp[i], dp[aj]+1)\n",
    "        return -1 if dp[time] == float(\"inf\") else dp[time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips = sorted(clips, key=lambda x:x[0])\n",
    "        end = 0\n",
    "        count = 0\n",
    "        for i in range(len(clips)):\n",
    "            if end >= time:\n",
    "                return count\n",
    "            maxium = -float('inf')\n",
    "            for j in range(i, len(clips)):\n",
    "                if clips[j][0] <= end:\n",
    "                    maxium = max(maxium, clips[j][1])\n",
    "                else:\n",
    "                    i = j - 1\n",
    "            if maxium == -float('inf'):\n",
    "                return -1\n",
    "            count += 1\n",
    "            end = maxium\n",
    "        if end >= time:\n",
    "            return count\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp=[0]+[float('inf')]*time\n",
    "        for i in range(1,time+1):\n",
    "            for aj,bj in clips:\n",
    "                if aj<i<=bj:\n",
    "                    dp[i]=min(dp[i],dp[aj]+1)\n",
    "        return -1 if dp[time]==float('inf') else dp[time]            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码已经通过力扣的测试用例，应该可直接成功提交。\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], T: int) -> int:\n",
    "        if T == 0:\n",
    "            return 0\n",
    "        # 按起点升序排列，起点相同的降序排列\n",
    "        # PS：其实起点相同的不用降序排列也可以，不过我觉得这样更清晰\n",
    "        clips.sort(key=lambda x: (x[0], -x[1]))\n",
    "        # 记录选择的短视频个数\n",
    "        res = 0\n",
    "        curEnd, nextEnd = 0, 0\n",
    "        i, n = 0, len(clips)\n",
    "        while i < n and clips[i][0] <= curEnd:\n",
    "            # 在第 res 个视频的区间内贪心选择下一个视频\n",
    "            while i < n and clips[i][0] <= curEnd:\n",
    "                nextEnd = max(nextEnd, clips[i][1])\n",
    "                i += 1\n",
    "            # 找到下一个视频，更新 curEnd\n",
    "            res += 1\n",
    "            curEnd = nextEnd\n",
    "            if curEnd >= T:\n",
    "                # 已经可以拼出区间 [0, T]\n",
    "                return res\n",
    "        # 无法连续拼出区间 [0, T]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort(key=lambda x: (x[0], -x[1]))\n",
    "        n = len(clips)\n",
    "        cur = nxt = res = i = 0\n",
    "        while i < n and clips[i][0] <= cur:\n",
    "            while i < n and clips[i][0] <= cur:\n",
    "                nxt = max(nxt,clips[i][1])\n",
    "                i += 1\n",
    "            cur = nxt\n",
    "            res += 1\n",
    "            if cur >= time:\n",
    "                return res\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort(key=lambda x:(x[0], x[1]))\n",
    "        if clips[0][0] > 0:\n",
    "            return -1\n",
    "        if clips[0][1] >= time:\n",
    "            return 1\n",
    "        ans = [clips[0]]\n",
    "        for x, y in clips[1:]:\n",
    "            if ans:\n",
    "                if x > ans[-1][-1]:\n",
    "                    return -1\n",
    "                if x == ans[-1][0]:\n",
    "                    if ans[-1][1] < y:\n",
    "                        ans.pop()\n",
    "                        ans.append([x, y])\n",
    "                        if y >= time:\n",
    "                            break\n",
    "                else:\n",
    "                    if ans[-1][-1] < y:\n",
    "                        while len(ans) > 1:\n",
    "                            if ans[-2][1] >= x:\n",
    "                                ans.pop()\n",
    "                            else:\n",
    "                                break\n",
    "                        ans.append([x, y])\n",
    "                        if y >= time:\n",
    "                            break\n",
    "            else:\n",
    "                ans.append([x, y])\n",
    "        if ans[-1][-1] < time:\n",
    "            return -1\n",
    "        \n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        n = len(clips)\n",
    "        clips.sort(key = lambda x : (x[0], -x[1]))\n",
    "        # print(clips)\n",
    "\n",
    "        right = clips[0][1]\n",
    "        if clips[0][0] != 0:\n",
    "            return -1\n",
    "\n",
    "        cnt = 1\n",
    "\n",
    "        if right >= time:\n",
    "            return cnt\n",
    "        idx = 0\n",
    "        while idx < n:\n",
    "\n",
    "            farReach = right\n",
    "\n",
    "            while idx < n and clips[idx][0] <= right:\n",
    "                farReach =max(farReach, clips[idx][1])\n",
    "                idx += 1\n",
    "            \n",
    "            if farReach == right:\n",
    "                return -1\n",
    "            \n",
    "            cnt += 1\n",
    "            \n",
    "            right = farReach\n",
    "            if right >= time:\n",
    "                return cnt\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def videoStitching(self, clips, time):\n",
    "        \"\"\"\n",
    "        :type clips: List[List[int]]\n",
    "        :type time: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        dp = [1e5]*(time+1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1,time+1):\n",
    "            # 状态方程的实现\n",
    "            for c in clips:\n",
    "                if c[0] < i <= c[1]:\n",
    "                    dp[i] = min(dp[i],dp[c[0]]+1)\n",
    "\n",
    "        return dp[time] if dp[time] != 1e5 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxa = [0 for _ in range(time)]\n",
    "        for start, end in clips:\n",
    "            if start < time:\n",
    "                maxa[start] = max(end, maxa[start])\n",
    "\n",
    "        ans = 0\n",
    "        last, pre = 0, 0\n",
    "        for i in range(time):\n",
    "            last = max(last, maxa[i])\n",
    "            if last == i:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ans += 1\n",
    "                pre = last\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dp\n",
    "    # https://leetcode.cn/problems/video-stitching/solution/shi-pin-pin-jie-by-leetcode-solution/\n",
    "    def videoStitching1(self, clips: List[List[int]], time: int) -> int:\n",
    "        dp = [0] + [float(\"inf\")] * time\n",
    "        for i in range(1, time + 1):\n",
    "            for aj, bj in clips:\n",
    "                if aj < i <= bj:\n",
    "                    dp[i] = min(dp[i], dp[aj] + 1)\n",
    "        \n",
    "        return -1 if dp[time] == float(\"inf\") else dp[time]\n",
    "\n",
    "\n",
    "\n",
    "    # * 贪心\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        last = ret = pre = 0\n",
    "        for a, b in clips:\n",
    "            if a < time:\n",
    "                maxn[a] = max(maxn[a], b)\n",
    "        \n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        \n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort()\n",
    "        stack = []\n",
    "        # use longest interval if same start\n",
    "        for a, b in clips:\n",
    "            if not stack or a > stack[-1][0]:\n",
    "                stack.append((a, b))\n",
    "            else:\n",
    "                stack[-1] = (a, b)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, prev):\n",
    "            if prev >= time:\n",
    "                return 0\n",
    "            if i == len(stack) or stack[i][0] > prev:\n",
    "                return float('inf')\n",
    "\n",
    "            return min(1 + dp(i+1, stack[i][1]), dp(i+1, prev))\n",
    "\n",
    "\n",
    "        ans = dp(0, 0)\n",
    "        return ans if ans < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        if time == 0:\n",
    "            return 0\n",
    "        # 按起点升序排列，起点相同的降序排列\n",
    "        clips.sort(key=lambda a: (a[0], -a[1]))\n",
    "        # 记录选择的短视频个数\n",
    "        res = 0\n",
    "\n",
    "        curEnd = 0\n",
    "        nextEnd = 0\n",
    "        i = 0\n",
    "        n = len(clips)\n",
    "        while i < n and clips[i][0] <= curEnd:\n",
    "            # 在第 res 个视频的区间内贪心选择下一个视频\n",
    "            while i < n and clips[i][0] <= curEnd:\n",
    "                nextEnd = max(nextEnd, clips[i][1])\n",
    "                i += 1\n",
    "            # 找到下一个视频，更新 curEnd\n",
    "            res += 1\n",
    "            curEnd = nextEnd\n",
    "            if curEnd >= time:\n",
    "                # 已经可以拼出区间 [0, T]\n",
    "                return res\n",
    "        # 无法连续拼出区间 [0, T]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        #First, we need to sort our data:\n",
    "        clips.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        #After sorting the data with starting time increase, ending time decrease (if starting times are the same), we need to define count:\n",
    "        count = 0\n",
    "\n",
    "        #Then we need to compare: \n",
    "        #we need the first one whose staring time starts from zero\n",
    "        if clips[0][0] == 0:\n",
    "            count += 1\n",
    "        else:\n",
    "            return -1\n",
    "        # We need to set up an chosenEnd\n",
    "        chosenEnd = clips[0][1]\n",
    "\n",
    "        if chosenEnd >= time:\n",
    "            return count\n",
    "        \n",
    "        # We also need to set up a maxEnd\n",
    "        maxEnd = clips[0][1]\n",
    "        \n",
    "        #In our for-loop, we need to select the one that has a start that is no-larger than the chosenEnd,\n",
    "        # In this range, we need to construct a nested loop to find the largest newEnd.\n",
    "        for i in range (1, len(clips)):\n",
    "            if clips[i][0] <= chosenEnd:\n",
    "                if maxEnd < clips[i][1]:\n",
    "                    maxEnd = clips[i][1]\n",
    "                if time - clips[i][1] <= 0:\n",
    "                    count +=1\n",
    "                    return count\n",
    "            if clips[i][0] > chosenEnd and chosenEnd != maxEnd:\n",
    "                chosenEnd = maxEnd\n",
    "                count +=1\n",
    "                if time - clips[i][1] <= 0:\n",
    "                    count +=1\n",
    "                    return count\n",
    "        \n",
    "        return -1\n",
    "\n",
    "                 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        # 跟花园灌溉那道题类似，本题是用最少的片段覆盖视频区间\n",
    "        # 栈里面存放的需要是片段守护的区间，而不是本身的长度区间\n",
    "        clips.sort(key=lambda x:(x[1],-x[0]))\n",
    "        sta = []\n",
    "        for c in clips:\n",
    "            if c[0]>=time: continue\n",
    "            if c[0]==c[1]: continue\n",
    "            while sta and sta[-1][0]>=c[0]:\n",
    "                sta.pop(-1)\n",
    "            cl,cr = -1, -1\n",
    "            if sta:\n",
    "                cl,cr = max(sta[-1][1], c[0]),min(c[1],time)\n",
    "            else:\n",
    "                cl,cr = c[0], min(c[1], time)\n",
    "            if cl>=time: continue\n",
    "            sta.append([cl,cr])\n",
    "        if len(sta)==0:\n",
    "            return -1\n",
    "        if sta[0][0]>0 or sta[-1][1]<time:\n",
    "            return -1\n",
    "        for i in range(len(sta)-1):\n",
    "            if sta[i][1]<sta[i+1][0]:\n",
    "                return -1\n",
    "        return len(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        maxn = [0] * time\n",
    "        last = ret = pre = 0\n",
    "\n",
    "        # 预处理所有的子区间，获取以a为起始点的最右端点\n",
    "        for a, b in clips:\n",
    "            if a < time:\n",
    "                maxn[a] = max(maxn[a], b)\n",
    "\n",
    "        for i in range(time):\n",
    "            last = max(last, maxn[i])\n",
    "\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort(key=lambda l: l[0])\n",
    "        pre_end = 0\n",
    "        n = len(clips)\n",
    "        i = 0\n",
    "        tmp = 0\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            found = False\n",
    "            while i < n and clips[i][0] <= pre_end:\n",
    "                found = True\n",
    "                if clips[i][1] > clips[tmp][1]:\n",
    "                    tmp = i\n",
    "                i += 1\n",
    "            if not found:\n",
    "                return -1\n",
    "            ans += 1\n",
    "            pre_end = max(pre_end, clips[tmp][1])\n",
    "            if pre_end >= time:\n",
    "                return ans\n",
    "        return -1\n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort(key=lambda x : x[0])\n",
    "        end, end2, count = 0, 0, 0\n",
    "        i = 0\n",
    "\n",
    "        while i < len(clips):\n",
    "            if(clips[i][0] > end):\n",
    "                return -1\n",
    "            \n",
    "            while i < len(clips) and clips[i][0] <= end:\n",
    "                end2 = max(end2, clips[i][1])\n",
    "                i += 1\n",
    "            \n",
    "            count += 1\n",
    "            end = end2\n",
    "            if(end >= time):\n",
    "                return count\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        # First, we need to sort our data:\n",
    "        # We sort the data with starting time increasing &\n",
    "        # ending time decreasing (if starting times are the same).\n",
    "        clips.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        # Then we initialize count (right now we have nothing to count)\n",
    "        count = 0\n",
    "\n",
    "        # The first clip has a starting time at zero: otherwise it is invalid.\n",
    "        if clips[0][0] == 0:\n",
    "            count += 1\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        # Set up chosenEnd to be the first clip.\n",
    "        chosenEnd = clips[0][1]\n",
    "\n",
    "        # Compare this end with final time.\n",
    "        if chosenEnd >= time:\n",
    "            return count\n",
    "        \n",
    "        # Set up a maxEnd, right now it's the ending of first clip.\n",
    "        maxEnd = clips[0][1]\n",
    "        \n",
    "        # In the for-loop:\n",
    "        # 1. Select the one that has a start time which is no-larger than the chosenEnd,\n",
    "        #       Within this range, find the new maxEnd.\n",
    "        #       Within this range, evaluate if the end of a clip exceeds the time so we add this clip could return.\n",
    "        # 2. Update the choseEnd if the current clip does not overlap with the previous chosenClip.\n",
    "        #       Make sure that the chosenEnd is not the same as maxEnd, so it is not re-counted.\n",
    "        #       Now there is a new chosenEnd, we update our count, \n",
    "        # then evaluate also if the non-overlapping clip could be added to our selection.\n",
    "\n",
    "        # if all of the above fails, we return -1.\n",
    "        for i in range (1, len(clips)):\n",
    "            if clips[i][0] <= chosenEnd:\n",
    "                if maxEnd < clips[i][1]:\n",
    "                    maxEnd = clips[i][1]\n",
    "                if time - clips[i][1] <= 0:\n",
    "                    count +=1\n",
    "                    return count\n",
    "            if clips[i][0] > chosenEnd and chosenEnd != maxEnd:\n",
    "                chosenEnd = maxEnd\n",
    "                count +=1\n",
    "                if time - clips[i][1] <= 0:\n",
    "                    count +=1\n",
    "                    return count\n",
    "        \n",
    "        return -1\n",
    "\n",
    "                 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], T: int) -> int:\n",
    "        if T == 0:\n",
    "            return 0\n",
    "        # 按起点升序排列，起点相同的降序排列 \n",
    "        clips.sort(key = lambda x: (x[0],-x[1])) \n",
    "        # 记录选择的短视频个数\n",
    "        res = 0\n",
    "        curEnd = 0\n",
    "        nextEnd = 0\n",
    "        i=0\n",
    "        n = len(clips)\n",
    "        while i < n and clips[i][0] <= curEnd:\n",
    "        # 在第res个视频的区间内贪心选择下一个视频 \n",
    "            while i < n and clips[i][0] <= curEnd:\n",
    "                nextEnd = max(nextEnd, clips[i][1])\n",
    "                i += 1\n",
    "            # 找到下一个视频 更新curEnd \n",
    "            res += 1\n",
    "            curEnd = nextEnd\n",
    "            if curEnd >= T:\n",
    "            # 已经可以拼接出区间[0,T]\n",
    "                return res \n",
    "        # 无法拼接出区间[0,T]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        start = 0\n",
    "        remain = []\n",
    "        res = 0\n",
    "        while clips and start < time:\n",
    "            max_end = start\n",
    "            for c in clips:\n",
    "                if c[0] <= start and start <= c[1]:\n",
    "                    max_end = max(max_end, c[1])\n",
    "                if c[1] > max_end:\n",
    "                    remain.append(c)\n",
    "            clips = remain\n",
    "            print(start, max_end, remain)\n",
    "            remain = []\n",
    "            res += 1\n",
    "            if start == max_end:\n",
    "                return -1\n",
    "            start = max_end\n",
    "        if start >= time:\n",
    "            return res\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort()\n",
    "        @cache\n",
    "        def dfs(t, idx):\n",
    "            if t >= time: return 0\n",
    "            if idx == len(clips): return inf\n",
    "            b, e = clips[idx]\n",
    "            if b > t: return inf\n",
    "            return min(dfs(t, idx + 1), 1 + dfs(e, idx + 1))\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    # 1326: 灌溉花园的最少水龙头树木\n",
    "    # 45: 跳跃游戏\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        n = len(clips)\n",
    "        nums = [0] * time\n",
    "        for l, r in clips:\n",
    "            if l < time:\n",
    "                nums[l] = max(r - l, nums[l])\n",
    "        # 跳跃游戏\n",
    "        step = 0\n",
    "        curEnd, nextEnd = 0, 0\n",
    "        for i in range(time):\n",
    "            if i > curEnd:\n",
    "                return -1 # 无法覆盖\n",
    "            nextEnd = max(nextEnd, i + nums[i]) # 更新下次能跳的最远距离\n",
    "            if i == curEnd: # 当前能跳的距离已经达到\n",
    "                curEnd = nextEnd\n",
    "                step += 1\n",
    "        return step if curEnd >= time else -1\n",
    "        \n",
    "    def videoStitching_bfs(self, clips: List[List[int]], time: int) -> int:\n",
    "        ans, n = float('inf'), len(clips)\n",
    "        q = deque([[0, 0, [0 for _ in range(time)]]]) # curIdx, curCost, curTime\n",
    "        while q:\n",
    "            curIdx, curCost, curTime = q.popleft()\n",
    "            # print(f\"curIdx:{curIdx}, curCost:{curCost}, curTime:{curTime}\")\n",
    "            if curIdx == n:\n",
    "                if sum(curTime) == time:\n",
    "                    ans = min(ans, curCost)\n",
    "                continue\n",
    "            # 不拼接\n",
    "            q.append([curIdx+1, curCost, curTime[::]])\n",
    "            for i in range(curIdx, n):\n",
    "                nextStart, nextEnd = clips[i]\n",
    "                if nextStart > time or curCost + 1 > ans:\n",
    "                    continue\n",
    "                nextTime = curTime[::]\n",
    "                for t in range(nextStart, min(time, nextEnd)):\n",
    "                    nextTime[t] = 1\n",
    "                q.append([i+1, curCost + 1, nextTime[::]])\n",
    "        return ans if ans != float('inf') else -1\n",
    "    def videoStitching_dfs(self, clips: List[List[int]], time: int) -> int:\n",
    "        n = len(clips)\n",
    "        def addNums(base, add):\n",
    "            ans = list(base)\n",
    "            startTime, endTime = add\n",
    "            for i in range(startTime, min(endTime, time)):\n",
    "                if not ans[i]:\n",
    "                    ans[i] = 1\n",
    "            return tuple(ans)\n",
    "        # 使用数组\n",
    "        @lru_cache()\n",
    "        def dfs(curIdx, nums):\n",
    "            if sum(nums) == time:\n",
    "                return 0\n",
    "            if curIdx == n:\n",
    "                return float('inf')\n",
    "            return min(float('inf'), 1 + dfs(curIdx + 1, addNums(nums, clips[curIdx])), dfs(curIdx + 1, nums)) # 使用\n",
    "        ans = dfs(0, tuple([0]*time))\n",
    "        return ans if ans != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        inf = 150\n",
    "        dp = [inf for _ in range(150)]\n",
    "        cliplist = [(l,r) for l, r in clips]\n",
    "        cliplist.sort()\n",
    "        dp[0] = 0\n",
    "        for l, r in cliplist:\n",
    "            for i in range(l, r+1):\n",
    "                dp[i] = min(dp[i], dp[l]+1)\n",
    "        print(dp)\n",
    "        return dp[time] if dp[time] < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        clips.sort(key=lambda t:(t[0],-t[1]))\n",
    "        print(clips)\n",
    "        tar=0\n",
    "        could=None\n",
    "        ans=0\n",
    "        for [st,ed] in clips:\n",
    "            if st>tar:\n",
    "                if could is None:\n",
    "                    return -1\n",
    "                else:\n",
    "                    print(tar,could)\n",
    "                    tar=could[1]\n",
    "                    if st>tar:\n",
    "                        return -1\n",
    "                    could=(st,ed)\n",
    "                    ans+=1\n",
    "            else:\n",
    "                if could is None:\n",
    "                    could=(st,ed)\n",
    "                elif could[1]<ed:\n",
    "                    print((st,ed),could)\n",
    "                    could=(st,ed)\n",
    "            if could[1]>=time:\n",
    "                ans+=1\n",
    "                tar=time\n",
    "                break\n",
    "        return ans if tar==time else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # def binary_serach(self, nums, FLag = 0, target):\n",
    "    #     left, right = 0, len(nums) -1 \n",
    "    #     while left <= right:\n",
    "    #         mid = (left + right ) // 2\n",
    "\n",
    "    def videoStitching(self, clips: List[List[int]], time: int) -> int:\n",
    "        # 贪心算法 \n",
    "        # 第i段的end应该在第i+1段的start 之前，即 end <= start\n",
    "        for i in range(len(clips)):\n",
    "            clips[i] = [clips[i][0], clips[i][1] +1 ]\n",
    "        clips_end_sorted = sorted(clips, key = lambda x:x[1], reverse = True)\n",
    "        clips_start_sorted = sorted(clips)\n",
    "        if clips_end_sorted[0][1] <= time or clips_start_sorted[0][0] > 0:\n",
    "            return -1\n",
    "\n",
    "        begin_index = 0\n",
    "        max_end = 0\n",
    "        begin_clip = None\n",
    "        while begin_index < len(clips) and clips_start_sorted[begin_index][0] == 0:\n",
    "            if clips_start_sorted[begin_index][1] > max_end:\n",
    "                max_end = clips_start_sorted[begin_index][1]\n",
    "                begin_clip = clips_start_sorted[begin_index]\n",
    "            begin_index += 1\n",
    "        # 根据max_end,一步一步找最后的数\n",
    "        clips_num = 1\n",
    "        while max_end < time + 1:\n",
    "            # 找到最大的那个\n",
    "            FLAG = False\n",
    "            for i in range(len(clips_end_sorted)):\n",
    "                if clips_end_sorted[i][0] < max_end and clips_end_sorted[i][0] != begin_clip[0]:\n",
    "                    begin_clip = clips_end_sorted[i]\n",
    "                    max_end = begin_clip[1]\n",
    "                    clips_num += 1\n",
    "                    FLAG = True\n",
    "                    break\n",
    "            if not FLAG:\n",
    "                return -1\n",
    "        return clips_num\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
